n=850;
m=5000;
k=12000;
D=[92,1,52,43,22,55,6,38,12,84,28,79,86,52,48,91,52,11,41,55,97,46,70,74,73,47,48,18,14,68,73,87,34,25,81,74,12,19,24,7,51,17,26,56,82,62,38,100,47,40,84,81,35,27,51,90,23,29,43,38,6,88,4,99,9,91,86,91,70,16,99,95,22,43,8,19,98,58,60,71,18,52,87,13,13,66,92,25,78,45,47,72,71,61,8,1,52,27,47,75,44,89,50,41,77,96,18,4,63,45,50,81,81,77,30,48,64,51,77,42,57,55,36,44,83,89,49,94,99,22,92,49,27,23,17,85,76,51,52,35,64,50,8,32,28,65,77,5,42,63,79,73,93,83,32,62,12,55,81,85,71,35,58,33,58,40,61,35,67,65,99,93,21,93,19,18,43,67,81,16,21,45,20,71,88,5,69,7,21,36,18,90,26,38,88,87,81,62,61,84,55,69,42,89,42,99,66,75,3,7,17,14,41,69,98,95,4,38,82,54,39,50,15,1,86,67,10,32,77,60,65,47,47,38,13,95,23,38,13,5,95,73,21,73,12,31,73,45,24,5,35,60,92,15,28,95,66,47,76,91,12,95,93,56,39,63,96,76,77,72,69,10,84,6,34,3,44,59,55,33,9,18,5,31,46,94,6,30,63,36,26,8,68,93,18,75,44,85,4,82,63,64,56,17,44,73,54,72,52,6,46,91,53,14,38,5,76,67,44,81,60,17,77,19,100,12,51,49,53,74,28,59,50,51,100,74,77,18,79,82,45,31,93,48,94,72,32,45,51,47,26,29,52,35,92,69,25,35,96,49,34,21,80,62,64,27,84,1,10,26,32,79,25,54,20,95,91,48,15,27,53,69,44,79,34,27,12,17,82,31,85,35,43,90,12,64,63,54,1,7,47,52,98,62,46,72,24,92,40,10,45,20,76,49,75,96,15,90,79,15,91,74,3,51,64,97,1,75,38,48,85,91,25,52,12,31,83,24,95,68,46,31,76,79,79,7,69,95,21,99,83,87,16,42,57,38,66,87,6,45,49,47,94,81,91,50,46,67,4,58,75,94,28,29,87,56,27,52,96,13,51,83,3,22,81,74,75,79,16,3,95,61,69,13,3,22,49,14,80,72,94,54,43,26,30,54,30,19,90,2,68,12,85,20,75,2,47,71,13,10,38,89,40,84,72,25,77,96,3,77,54,76,56,32,8,28,28,74,22,80,42,11,39,22,43,16,88,58,77,43,32,48,93,97,30,81,88,51,59,93,90,26,73,34,82,85,17,21,91,35,45,4,3,87,99,26,22,94,1,71,87,100,39,23,91,96,4,79,85,23,76,65,92,77,48,75,24,36,50,39,14,19,73,78,27,80,63,72,37,95,34,63,14,5,10,85,58,29,30,77,33,42,87,18,35,15,27,26,51,41,27,92,81,33,42,3,36,36,59,77,16,49,71,56,52,47,29,77,54,84,8,44,2,71,97,62,35,22,66,7,22,25,72,96,64,85,50,53,44,82,28,60,16,10,21,72,23,56,13,36,45,1,67,62,95,90,84,76,82,28,62,58,21,75,50,45,100,96,87,10,30,14,9,37,23,65,7,39,46,42,52,72,1,53,10,10,4,67,43,48,70,48,46,7,52,51,4,33,28,69,32,37,91,65,6,100,19,22,41,39,34,48,93,43,13,87,1,68,10,55,74,30,26,67,50,55,32,85,42,87,20,48,37,34,73,42,75,82,47,58,19,58,66,7,81,64,41,83,80,48,72,21,21,59,62,4,63,85,40,89,37,87,92,49,27,46,31,97,80,50,76,56,34,83,70,69,86,100,30,85,96,67,26,21,65,86,51,7,91,65,8,88,11,14,93,92,77,72,69,6,70,12,32,72,40,47,42,28,98,1,26,38,36,36,48,20,89,55,20];
T=[5863,707,195,12369,2711,23685,1033,2570,3224,8066,436,2993,14268,25390,20373,5897,1204,11696,8887,14726,19807,970,31367,3418,3,18884,68,3177,33640,29931,4874,7435,13906,644,24754,5021,13106,11131,1,24566,2766,1,7548,3553,166,8100,20491,4772,14098,576,32748,1083,53,3432,22938,4623,228,9544,11637,1196,2432,1992,6545,238,8765,17582,103,104,15961,2509,5118,11651,2102,44049,21051,7789,16033,40651,62,3010,3471,3431,12679,575,26523,8727,668,6497,21840,4342,70892,655,4836,25837,667,2157,14682,3099,121,117,15084,25298,3642,2939,4417,5275,2189,2695,2125,12369,10812,161,2354,5017,15965,219,48623,8124,60554,33515,5906,354,1071,3184,52,10342,4070,46025,184,4076,12271,32,28751,15878,12125,17401,21022,9672,14725,1,394,40991,2486,971,189,4284,14452,2860,17994,5244,11130,5100,599,497,508,3079,181,7422,196,101,59066,11989,491,329,3464,2061,10861,202,1539,52674,51114,3241,7998,9438,17527,4974,1259,12575,1430,63,2719,26043,8465,16287,249,13101,1188,5377,17280,9837,1842,428,2214,347,988,737,7245,404,2710,9846,2384,2623,28570,2681,27137,2362,47265,9166,886,33094,4,144,413,22364,11275,380,5657,27404,5033,27323,36422,6270,14700,9160,3277,1093,4241,27585,688,2317,6477,1,6191,14420,14156,30416,4270,3016,663,2220,9708,7374,3273,2808,130,4333,39476,1933,30729,16510,5374,29458,424,4086,17,207,725,1657,2630,47896,22789,295,10043,37490,23129,34142,6787,18515,2587,23588,32950,27804,7152,8206,23264,34885,5816,1339,1541,1159,43426,9893,2212,3591,40073,6282,57549,134,904,26478,5567,44520,8640,7634,11471,11149,5295,5134,5122,17520,11968,1,9018,9708,242,13767,23859,246,4534,1013,2242,19622,45688,4107,120,28638,19262,11491,732,2698,7873,15847,8275,2332,1,14500,2725,1694,12247,30538,14395,1029,9808,17,9236,8903,29470,39,730,2944,1023,10922,584,2304,20564,10125,4251,1071,20906,21756,11124,15529,11218,18389,82430,19541,22727,14760,150,87,6986,494,2929,8707,16140,7401,2481,615,653,2876,19837,10614,2659,427,7551,40267,18363,13776,3828,2444,14527,1448,37973,5,19198,9371,6416,188,3444,5940,51,438,8837,15672,11776,9198,1251,4799,1,5703,14776,30951,777,16864,11196,7566,344,13688,12581,1309,4668,11999,4040,889,3516,33090,1,5047,1268,1468,141,25618,1300,152,18826,1551,3850,12662,8889,24382,5507,1,1241,680,11181,41625,19969,16103,1071,2229,28968,1792,5330,6093,25201,16482,11969,4963,11180,776,3423,2700,4711,25365,7214,13669,1126,259,7163,7358,831,129,24122,35025,5137,70635,10195,2221,2859,7002,9902,14,6221,3710,1,23725,3194,46,21028,7488,20481,53021,1,834,2287,4449,25948,38359,8307,12571,12509,8241,2153,369,11381,17344,1059,4878,9844,491,980,3468,504,18038,15580,6015,3587,363,13810,21438,22894,14597,7655,1582,55903,23984,3170,4553,1986,8836,51781,10876,36309,10434,38,3631,960,4175,30022,2091,5962,2032,2890,4096,7564,10230,15429,6448,516,132,1,1164,35825,12912,9375,1040,9734,506,13435,697,2057,25018,28412,1709,11187,54401,2857,12150,12028,1075,42182,52211,1,7563,14108,403,33510,28874,12,7870,7111,339,2866,41941,780,185,15401,8319,10250,8203,4370,21512,6003,31393,3978,1,675,2449,929,5074,44501,1022,13684,10144,43,38858,9803,30826,930,3484,19062,8583,215,23352,111,14731,712,6129,493,37940,46628,5482,1023,4948,6236,8149,649,11224,11533,1117,16629,11298,12126,38649,5286,42,29823,452,4484,1148,9796,6770,5299,8768,6108,27506,5593,979,3319,8129,16806,38302,8448,8,23983,48830,415,237,30878,742,244,5108,9486,1986,1,3035,6948,3361,15559,6218,4971,13110,1561,25675,20733,362,2629,9989,263,1519,13639,13918,890,24795,31935,458,6532,6693,9521,12522,26407,2653,5956,4998,15858,9430,34213,1892,444,4108,88,15951,6862,100,3588,18,32206,11007,3982,6585,143,501,46027,13456,851,46,8378,17821,42404,26087,325,21470,3194,4854,7479,15200,2187,7043,11708,18249,16057,28114,823,7703,5676,3861,31075,12831,12366,357,12780,8169,984,7080,7533,93,7211,1902,60000,1519,12673,15366,1364,20743,1,9200,1222,803,4624,28813,7019,32291,6544,34189,3828,4214,18067,34985,1055,25761,6790,15738,6880,8850,389,19783,11849,431,14,21802,3860,61137,7250,2831,35110,10883,37,4808,23330,70,13359,692,297,12556,1868,7131,6319,11170,14916,2506,18530,6,7213,9218,724,3304,18922,32293,629,4916,3938,4488,2520,7633,4357,8064,35111,26306,17647,38699,604,5808,637,76,25503,63918,4860,9804,4240,982,54973,14905,8655,1191,44077,53460,10530,869,94,22899,12188,207,442,7038,306,818,2665,13801,41084,29336,27379,12216,19655,34212,3386,3703,6893,489,1400,24966,52,8915,7693,79,21083,10726,3115,3117,2592,1501,5295,13147,1354,6820,557,8283,26047,1153,1586,18996,25575,117,462,14080,22615,15541,12570,11603,3193,15707,13809,1303,16938,4623,645,8664,3559,32466,1,1922,1734,17638,716,16924,2340,17491,3923,403,4260,28550,2289,7464,10826,6061,1210,4994,3393,3782,9175,7008,8539,26363,317,3625,10138,7421,3901,6815,13497,2934,1369,14735,13125,2534,2795,3128,3014,24942,5587,652,16425,859,2213,161,966,22670,9,3035,78,21179,5277,43580,879,3630,10766,9614,2407,43,1271,11132,50077,4072,414,10152,2888,1040,1037,31054,8957,24216,8532,41591,978,5598,6695,16096,8199,2233,17461,29,2384,3977,24957,591,62066,69,7725,553,6357,4032,16820,20028,9398,1148,16822,1709,10209,22319,20851,29065,11781,17881,12803,21976,5148,519,2097,6834,9139,3841,208,776,47838,4833,7275,1666,3822,1564,19160,1095,43,3351,23836,1582,3212,16133,223,11325,25731,62747,10782,30359,37,5620,21468,18201,33920,3480,14673,113,359,2471,5087,7236,7204,1,15234,16018,11857,29051,1394,24934,8891,267,3998,1030,1282,1752,5020,201,15191,11073,1333,36838,1234,11752,49,1233,5493,1936,5641,2219,14679,2787,7117,2249,34951,128,7577,818,5584,2260,591,468,2220,49663,11625,10694,43011,8408,907,2295,15289,10084,971,10405,4249,4010,13808,865,4745,69655,2609,1106,4985,429,44202,12917,3059,127,19629,50960,272,774,11988,1631,4920,26275,18106,3702,9988,4989,179,13140,2058,4058,1126,2032,1048,9733,25501,1126,648,2818,8015,13451,1063,100,678,724,5480,17476,1217,19122,188,285,760,2105,14106,2333,1245,1611,32,14372,12397,9435,5367,94,107,14155,1043,54,2053,51,4117,12721,908,17032,15830,13996,1931,6670,2095,14471,2641,23705,1400,20571,3048,46,2714,2779,453,52453,8122,15497,5594,9770,27121,20860,1999,30,333,425,34883,958,21687,10317,15980,3807,31523,2161,4192,6464,37940,326,261,22182,12194,77,5736,5025,44654,112,15724,4263,1929,673,4143,18524,379,9871,32115,13711,10010,1249,3154,259,150,7512,1614,28891,12183,8796,338,10225,3519,7191,4574,19060,20729,2046,9413,643,7264,6228,3568,37442,8330,21533,20502,10623,969,118,1617,1333,20188,19578,3999,7660,60,9130,48525,5855,38291,16238,650,9300,1212,12267,23763,25337,15335,323,1,5524,12052,1183,2461,780,21959,794,3690,25785,17666,5691,60319,37640,587,286,9642,13943,13853,29766,536,3966,26042,3390,7209,8696,6734,9103,7379,3327,8374,10408,15588,1557,72,1142,8099,8742,2434,3571,558,2792,12686,13726,7789,1488,4533,22179,1398,12147,18427,38237,10807,26358,1485,56181,19284,17420,4273,15580,3323,20007,10254,7576,8552,9025,16278,61972,247,8921,6625,7595,12988,19992,1801,40454,11084,34098,6652,1125,15062,8132,1595,3781,1422,1088,44,2064,7879,1005,29106,8265,16550,1523,763,6408,4330,8425,1092,4675,7649,1766,19349,12426,10092,5294,190,46,2813,8904,287,7197,21578,114,7,2227,3979,370,13112,14361,11390,5524,3633,38138,11932,19870,4146,16524,5550,32450,29408,27140,1297,23716,11292,8165,61589,8355,246,1818,2540,10835,9159,14372,2815,2334,39264,2380,11973,313,23180,12436,1619,1842,3064,6591,2873,7777,4839,1879,4575,13839,3876,9923,1046,9831,24902,3280,3063,2132,451,4555,1945,15275,358,51176,51228,13901,3823,20539,7516,381,557,17909,61254,13473,43,10559,840,71,22380,3846,621,2403,2619,12067,27378,2719,4058,40798,16600,822,1032,30396,1209,4720,6154,15290,3836,14120,4479,1072,5842,6791,8891,9264,236,1611,606,22862,277,3321,6590,2501,3104,316,3702,60310,153,26319,1927,1875,8456,633,23457,1924,635,8552,4789,36909,7865,5547,4299,4408,1923,731,29397,14319,96,1061,23144,2050,3713,51,2906,3104,1455,1,592,15477,3970,2687,1442,33900,3630,1256,15265,1036,2069,14296,3091,12627,4817,57,23939,11782,10141,6657,3309,6735,3851,9991,5116,1503,7561,6201,15418,699,1,46414,4955,9059,16640,978,2752,13105,2657,42054,82,20093,1998,13952,49001,8128,3028,3781,3304,104,1372,15311,2888,13062,25,4874,24246,12025,2260,5934,26530,58830,34380,1770,23783,6674,43722,1302,5,70,2128,12432,7431,25854,5042,9066,634,1989,17898,6085,7330,21573,12706,5008,45695,46782,348,31226,3141,2706,13419,8149,9170,3544,1737,2148,388,51,52911,9572,23043,355,1233,7433,2253,462,303,1448,32,4024,17837,7147,7033,1434,6557,29729,466,39,1013,2056,152,5687,3473,14707,8908,7361,806,5971,9200,29986,10177,8659,1401,11490,4546,19739,175,4280,2603,86,48466,1167,41110,13441,4227,3536,20416,37467,2073,4119,33002,9441,23798,11524,189,23233,1228,8142,27010,39201,1481,1195,24061,5006,883,19439,19962,1939,14264,2548,14518,22710,510,4591,5434,24899,4142,341,37689,5557,490,9555,248,42652,9353,2701,16258,2185,8718,11800,30335,346,38853,446,2960,2079,4686,807,15543,2734,13437,53,26367,3253,6783,40609,1515,23964,15407,7392,19175,5039,14853,4726,3206,9047,906,149,12673,17127,28616,4678,54037,985,35381,8950,113,3147,919,8607,11672,676,23843,24197,2853,18,1020,7851,35,13329,363,243,2430,1749,35756,411,126,3269,4023,8429,16515,29661,1626,13359,36725,3471,1084,431,197,1166,41205,5185,1286,614,20460,11109,47038,3377,1169,44934,3204,1805,17200,1377,10293,67,414,1927,231,38501,3596,6881,52588,17570,622,11679,21393,2590,18302,16777,10860,2673,8483,1924,2464,15665,19530,35013,10543,6556,8484,1973,77534,155,1434,1722,7008,39068,267,25324,16683,794,6957,34283,3651,9547,7802,3549,2263,3177,17148,4389,5316,15487,748,3567,31840,26924,1305,16355,24353,1151,404,1489,6695,23124,735,2080,14625,9493,916,587,36,32903,2508,430,570,1,33036,39,9218,27694,4965,5072,33517,1367,3566,27140,67891,28884,3540,4290,8135,396,12818,586,7621,94,1880,995,11912,52,542,174,562,31629,1534,65927,7926,6925,2033,1819,18638,946,11040,55697,3829,4046,11538,895,3814,57326,4230,9307,10316,15850,2575,7,17040,28663,5315,13767,2209,13497,4700,4861,280,27074,9337,8861,4328,17378,38961,2283,612,254,16,651,27026,37912,1422,90,25501,1883,9652,34126,27394,906,6862,50,33488,25050,18494,70993,53501,5314,1736,42240,29482,3605,2593,3896,1,237,2232,3589,23219,2777,3570,542,839,3780,94,3639,3142,3046,1703,22791,19576,5485,27060,28,9441,1804,10864,1032,2800,1687,1274,2505,28022,2816,19400,4744,8061,17281,14351,6235,1684,1190,18465,1177,796,40699,1540,2055,9101,2901,5188,13691,2468,1312,19458,4225,279,24501,9937,1387,1571,4122,8863,1816,1144,60413,607,7192,4173,5264,2149,51232,12113,364,3045,6119,5755,23965,10968,4147,258,43,37861,4120,16560,28183,42114,23284,42896,23967,970,26844,2188,29776,14381,5653,15987,16852,14526,3002,15237,16949,5784,15291,12880,5873,827,446,2300,193,6964,7112,15264,453,147,18990,1697,5037,8237,657,27428,1261,40688,6038,1201,6460,447,25888,27693,676,5586,3955,6608,7113,2036,8329,36701,4669,10649,25003,2815,25252,5492,11264,23738,2344,11589,976,3428,86,1667,339,14763,22685,8429,4457,3063,17642,12247,40158,9360,4675,22651,1,11747,2030,2069,264,11835,18286,7746,3846,3483,850,5566,6391,10861,10574,1645,3256,36562,962,39572,21099,12,1646,420,27642,3361,4898,1065,5688,34809,2532,20221,14345,1643,17917,15420,16522,14675,3607,6929,990,3609,116,2314,14843,8638,3639,3043,10173,17143,2043,10784,34985,6297,2365,4238,2296,289,554,380,1171,10744,3497,8851,102,370,2632,4439,2244,2000,63709,2274,7228,6361,69,401,32859,2390,4692,26906,117,5908,649,31016,37,23522,22100,322,425,16943,10564,896,2,15310,9027,3116,10237,2761,41258,331,385,10907,10203,23491,9749,3738,629,1173,10518,3054,5618,4063,2931,3434,4595,501,10337,8028,14111,2145,22547,9196,8611,20829,16385,20983,12502,11705,8560,22237,799,679,12415,2194,3070,21020,1796,712,1018,1207,3985,4891,3962,20270,3436,63125,23246,91,12441,14329,2995,413,11615,1554,17623,4273,22754,2329,4574,9018,35623,102,12020,2089,26224,30721,12270,16169,3569,1,146,5070,272,10293,55,4557,667,16446,1,9006,2054,16848,63526,4417,9928,1251,4732,8591,281,25356,6193,3158,5499,838,522,9841,19490,1992,43717,13778,40181,7783,38116,13020,3307,25062,11291,9357,27187,31352,712,5307,388,1768,18794,10285,6660,2765,21752,2701,1635,21578,17520,5005,15320,1113,628,11425,15258,4050,3904,10481,2492,32393,12285,8711,826,7,5539,1372,4351,15586,34729,17995,698,58735,20302,149,16262,7924,4833,2501,6915,10619,1459,511,7272,17023,3885,5378,5326,7619,469,2118,1327,38045,19663,2138,923,19006,14502,10401,6242,7858,6035,9540,133,13822,1192,1584,3590,22703,19274,12882,7825,4492,5524,16257,58616,5260,1832,1305,128,1836,16099,6939,5972,14705,7812,5939,21679,6928,707,1391,17,40162,26924,19475,87,43652,5765,20144,8647,2268,2932,7704,4920,1695,2453,16237,479,4720,4341,1270,163,12601,11765,48719,9846,667,5940,99,7009,4803,1,480,7996,3323,78,704,11213,2131,4060,89,2290,19215,14258,3115,1,1751,4706,880,8980,792,12940,493,1927,14674,20417,479,2758,15167,834,2575,279,23120,34855,500,21,235,36,14110,8261,854,1356,14698,932,449,7442,10989,8220,17232,2125,2097,1024,493,4524,50,26723,12775,3438,1369,40182,4672,8970,2843,7642,20286,22550,6596,1,1635,13051,11229,1403,16120,10491,3862,713,15178,629,2004,4441,1,849,2437,4268,6522,3872,54810,4211,1070,3618,227,2675,3154,36719,6420,1456,10298,617,103,28055,5258,17473,26538,38786,15,2846,1108,504,16118,2609,1293,37212,5265,4411,538,229,3458,13949,227,26586,23326,761,18004,5255,118,11,7281,48821,1852,9045,12115,4511,2595,18381,5612,14899,23093,5503,7863,466,12278,3173,788,31507,28623,9801,6131,27329,7996,9721,1548,7735,22,405,11751,28040,1,34969,40966,12219,14867,238,842,1191,611,9039,12947,884,574,4457,4549,10884,816,1244,3799,2280,4511,15224,3359,3318,4609,15502,280,52826,2176,4617,873,4796,1,38,7933,1,647,366,3150,3770,2513,301,3461,31442,4736,13114,41814,21182,4737,4897,141,3298,10593,1061,1163,1423,12527,21997,12724,13311,6949,11929,353,883,30371,1035,191,12034,1281,13387,40,14639,830,11088,1139,4128,2484,1738,18880,712,3173,22375,3359,11050,1568,9063,870,4623,2595,4245,8571,55,162,30986,535,5760,6658,584,4812,8457,6157,587,32280,6116,2192,11578,1840,2874,9135,1248,17513,13455,27834,24708,3576,28355,14553,968,970,38591,18995,25043,25,2349,10229,7766,9519,50,26013,2017,4040,27989,20605,325,26822,21056,2834,42658,35334,15539,7369,17,4869,7418,13237,709,26254,8910,2361,231,8021,12185,8451,2579,22383,2796,10242,23000,24792,724,1689,2927,133,4664,8896,8419,13415,100,19899,1036,12360,5502,14014,11951,2245,7751,8598,6789,43149,7219,9717,3886,5724,650,1419,13078,2309,48,4696,1257,6892,10314,2979,909,81,7,693,4407,4991,251,3207,30220,1635,22048,11729,1319,46665,6915,4080,27113,33541,3743,34457,10331,5328,13922,651,594,16798,10289,3375,14396,3934,46133,12886,64219,3946,6656,6304,28383,1621,24987,4825,355,8735,13338,17875,26818,170,21886,50717,618,18689,13911,1977,24061,1228,20997,1002,6227,9229,3723,92,3706,4991,8878,149,1468,62920,9396,8955,10993,4875,1720,22769,233,1,13528,2235,13442,973,8649,532,1697,2779,2491,1847,33735,22503,1734,3775,24594,12255,400,19751,14030,3224,2798,3025,6541,1360,3142,10755,3095,16453,4599,2410,5438,8200,9755,29102,5853,1,111,29671,13332,11271,10231,3559,7463,22093,32481,16466,2324,2236,61419,7161,1967,2362,8042,199,1483,9269,32527,3389,38361,2318,28753,682,667,323,34255,122,56902,39862,2288,700,17031,352,1227,14689,2688,10456,52633,2271,1431,9339,9014,673,39559,31307,28,4021,2322,24,6330,391,13721,14457,7497,16099,20008,29087,8924,2140,10361,4702,16188,4617,38901,466,1596,11029,2428,3390,1967,839,3357,282,37914,992,1962,13894,16157,2913,1455,8370,574,46119,6536,2212,3379,11115,15134,11599,2824,27258,7015,27412,29449,1860,728,2593,1476,10788,3758,22505,3233,4221,5638,9680,722,483,28171,5599,27660,118,4916,4367,2252,5514,1255,64822,8423,40508,55822,4852,32296,11087,10772,554,709,1635,19041,3099,3551,1478,41839,5319,9127,18408,4317,237,1403,4160,21039,7822,28370,5661,5347,1769,1062,40561,639,19228,2591,8792,52443,10036,338,45646,8972,14405,875,935,9358,52,4712,16986,3603,929,1064,10293,2306,1865,2316,6163,1124,3804,13756,157,753,1074,20218,16728,25435,26680,2219,9484,2450,29802,10232,12941,3127,27470,75,6601,17220,15422,10038,16634,2897,33693,2044,23171,56,4493,13347,13,2116,19446,11257,4807,5657,10,13033,14321,31301,13569,6868,25668,4447,17241,45757,3150,25852,7658,7005,18322,31128,6730,15206,453,8624,14250,4856,911,164,19847,145,3638,1424,5650,9358,667,13881,717,4905,1204,53133,24151,4783,16930,38,264,4690,1101,15415,13974,312,2876,2759,6424,47,1044,14608,31457,8980,1180,3392,6559,1,10832,22240,31334,6152,26534,17783,18480,3199,538,12266,2377,7039,2333,10943,6533,2504,75811,9012,1219,4876,4057,2469,18343,7570,1383,186,2100,10804,3782,2080,2150,48,3017,1626,31934,3395,18040,2806,25964,12993,55564,33196,12837,35381,202,344,2486,2947,1707,11241,7252,10373,1528,1963,6279,2184,20718,2982,711,96,1388,3396,13465,8151,10074,4460,19063,3086,9103,9310,4073,8046,16170,6759,12120,16346,1859,391,1932,15994,36460,10823,873,8042,85,914,26304,8245,51249,20535,33,7026,3096,55831,24960,2655,20166,1236,13468,15745,1895,8005,2878,28842,8638,8174,456,18491,8390,1910,5407,46,1,478,1,819,7361,44595,332,665,38453,21902,1191,18931,28104,8477,4372,9099,11907,44,5497,553,91,46601,11334,2756,25190,80,6242,10937,3063,11440,22632,1579,20542,1652,23,12276,819,9443,13655,4882,29087,10041,595,6473,1683,3998,12138,13891,14267,16004,17445,285,6901,14363,87,18519,10742,10621,528,8492,6663,1909,45270,2178,21493,5254,2021,1426,690,14245,4021,808,10963,1419,872,881,31292,12425,16078,4324,886,3774,6072,7108,16588,9422,3800,23275,16653,2017,13844,3578,41,2569,18293,1478,3365,4654,183,282,2287,1692,10336,11656,5920,9460,33981,4496,11927,14671,21564,1810,2223,1729,1922,9027,29385,2386,19906,23408,2410,74,1541,1358,4403,5654,36568,975,1043,895,23698,5755,1,8332,15632,19138,31525,16741,31985,3200,4972,19,14816,1,5817,34807,9397,5899,4172,22472,765,613,26,2782,19893,5511,24265,210,5544,648,11848,13841,44907,1134,13574,628,23417,8827,80,15934,3225,4035,26884,669,3583,14674,192,14979,6848,2270,16752,4923,87,33792,351,5285,817,20078,7326,2987,1730,3331,35642,13995,5709,10604,400,512,4435,7349,9422,9651,1802,294,29603,40579,1711,38294,17011,1188,4297,1631,3879,14831,9701,10050,26775,13506,3954,269,6493,118,417,3710,1367,2839,655,5082,16335,4584,5520,36,16506,8838,7330,2995,4924,21781,5250,2782,11188,2595,58999,10985,4576,3800,7632,3278,174,36067,11658,41723,17707,7157,9638,198,4482,12053,7097,94,5299,14774,9221,535,11195,1,7141,8582,4815,1060,5319,1853,425,2065,7894,22867,685,19261,994,3139,11698,7852,53764,724,7949,361,187,3837,51153,1,55592,13047,3420,13140,6584,6988,3163,4925,521,39459,2301,11248,12932,29987,1556,7154,1399,189,2232,14413,2961,15601,2337,7143,17872,10368,27626,247,9713,7533,326,280,9418,1588,1692,3202,16229,1857,26170,41350,16203,171,902,293,5775,5820,1782,2307,804,5612,12060,38706,20046,5461,7498,2086,1650,15841,2169,842,586,26237,8326,1804,3489,214,20622,14436,13155,48730,4579,29505,7673,1711,6839,33567,10685,20224,72,2762,6969,1616,12133,4049,4903,1017,299,1787,6987,6366,372,14313,617,2110,7617,7953,114,2714,14618,2395,3346,455,28930,6118,28172,652,1558,5903,19938,18900,39,2438,5892,14829,4069,22151,48517,13733,3000,19387,10615,210,17436,1506,188,29992,14635,2840,7415,1,15609,250,4779,2026,6869,308,16205,5457,65,2244,6941,14,20168,19315,3996,590,30930,1783,3544,4525,8344,11094,3546,8497,18084,27415,3538,16861,1299,4299,11946,33604,5493,1836,9375,26419,14034,663,5391,2600,11312,34169,15864,21980,13789,1883,1908,1088,19596,4837,20465,14471,36034,7320,111,37334,11573,14605,15359,46427,655,39868,1632,1251,5158,13251,33342,3541,11069,8930,11322,22815,251,166,492,26017,6216,4449,23674,7027,645,16876,416,1228,19719,59488,21380,840,41915,12457,1082,23703,1520,9016,11601,4746,1811,33243,31979,14549,2547,6188,10195,10618,65557,8011,3847,11848,3263,7228,2802,21464,3538,9502,31498,39431,835,4773,13800,36364,13520,3341,32340,6828,71,8929,1285,3803,18976,14922,8082,65173,28718,10125,6431,437,209,20351,1525,2822,25185,41607,269,4039,1188,39171,17171,2653,269,24,26785,30965,52207,10854,12861,9668,597,2274,8145,1063,48960,19891,1747,3139,30486,15248,18169,20095,12855,14276,6310,54,11834,125,10174,4187,4069,18808,498,24149,11772,2483,384,34207,1434,521,17,1153,5816,1026,34368,5304,1914,7576,6876,1922,24011,4097,52705,2459,4036,5421,110,131,1,27083,8272,9949,36439,27192,14914,1959,388,562,9824,10169,1248,6809,27868,23683,4558,1294,12752,60,6906,11263,10502,9299,2855,5690,17204,23104,533,1029,5306,39742,72,6140,8115,11800,2616,5854,5940,38678,4316,11933,11421,284,1742,135,295,2767,229,1355,27335,7207,6596,15660,25978,26795,42095,751,1202,790,77719,33170,27633,642,19392,7784,23840,392,38,5388,331,2341,19552,46378,34461,6474,1992,8258,41593,24996,36186,2095,1926,31433,2516,14756,10846,15688,646,124,27224,3798,19216,49848,2136,169,36347,2235,2454,22655,743,661,25198,6984,864,5057,10600,1183,1154,1568,3062,339,4265,10533,9301,9191,27795,10182,21637,22964,4355,31492,21966,1192,500,366,7002,11591,32794,27550,7232,24315,4512,3908,1453,14483,317,32772,1570,47078,22229,5396,20985,3112,367,53320,43,15283,6989,1431,531,5503,57,1964,2233,16905,615,11664,3286,14000,40611,1473,225,2867,2124,2808,128,18062,15723,13243,464,6596,32471,11241,10739,12104,11971,3490,25935,7251,46871,14057,1173,6846,1056,7466,4792,76,35739,22955,10480,11988,44053,15435,28356,3970,3169,784,6361,30069,330,28230,33662,40794,8922,7208,58540,27122,7321,2702,20381,25245,1,4563,172,28800,6554,5147,16082,35421,2594,27214,16635,4741,1111,15282,350,1518,29321,58647,8441,40692,782,658,758,15952,4950,4061,17774,3258,15266,32211,119,26873,1615,5470,2083,6096,2613,7791,727,15670,1814,46616,618,10759,41561,2533,910,5864,19905,11798,2702,1862,21793,1217,4071,342,51182,11759,356,17927,9757,7361,3266,29682,7099,32680,4234,6741,232,3343,1,758,310,158,759,1332,1167,32540,8782,804,2517,582,25220,17525,4859,849,688,10190,32655,600,27766,599,2737,13409,13751,1,9211,2517,5366,15928,49233,36267,9391,37092,4682,6587,13925,29646,10106,15023,3836,304,1294,8848,2193,6064,8976,2405,10,151,2499,3297,50869,23459,10733,18655,21724,11605,58,871,4188,2583,2403,695,58999,13139,7267,34395,1975,5541,801,854,10367,2526,2914,126,8317,2446,16567,15204,43543,1,8785,1896,38,33699,1976,1306,6658,9814,587,11475,28591,759,204,1891,11236,395,8708,1,32249,11344,1778,6020,8815,999,32898,12954,1116,1489,2292,9320,2660,958,1507,4076,14482,19049,3540,6468,72,6946,4807,6054,27573,12162,6074,4252,612,4765,2173,1866,8736,2014,31083,508,12188,25103,5948,16071,411,3135,1979,11321,505,283,5125,369,15451,415,3266,19,3672,1692,1027,982,22951,796,21118,10219,3751,97,19081,351,2726,42369,2941,5306,3843,679,2416,14102,1264,12509,4776,7175,4976,400,7263,471,43849,56261,9046,2406,34337,26712,137,13400,41261,16706,2560,6371,25790,543,1,473,2275,5237,3646,6842,14592,15136,1474,16838,8260,28211,46620,15008,8433,713,2503,1081,22754,825,23680,11579,9476,16510,6186,27576,2372,1170,3872,10181,542,6123,1758,1436,1225,16514,99,5447,23897,49568,25735,26870,766,308,15396,7161,4825,1,3487,26567,40785,2346,235,5876,2664,12492,32541,2977,527,9804,7997,721,3090,4253,12280,1958,10728,4772,4537,2167,303,7361,3184,5618,34832,11374,2125,19647,665,4292,1590,6605,12386,4038,5164,6854,826,6598,14340,13531,19005,25171,30582,9350,1069,9502,1939,1333,1110,776,3561,15223,6771,22672,787,20830,5945,11029,5787,52143,13684,2065,7329,2917,10617,30799,4782,1027,10463,4458,30178,6737,2738,96,7164,7943,980,2498,3020,157,5302,8230,21537,431,3103,80,2412,7330,25955,4458,12833,43570,23057,336,4495,8176,1721,1659,3896,11644,11085,20998,2701,48467,11079,8605,2426,130,9928,2866,21075,10135,10762,10434,503,11213,9674,145,13074,6160,12230,140,361,15806,493,7121,8565,1857,23754,1082,11803,3535,10238,9143,11591,1344,6522,9709,43,16584,1087,6169,8391,5845,12774,19005,44489,8658,4319,3898,255,4680,20944,1328,3750,17536,15849,60458,1597,26077,10644,1992,485,900,2776,605,415,11131,5348,29141,3620,8229,8886,4564,6219,8267,43171,37411,3130,2515,12907,1659,10927,21326,22058,2084,1,611,14291,17203,1247,20383,1827,17523,17485,1854,115,98,593,32799,14507,5131,150,326,7805,2939,1368,8907,10726,800,3096,3847,1259,5159,16373,31,47857,15847,5304,18166,24710,1607,6560,236,15679,3016,21389,957,3355,1243,16150,3840,3828,708,21509,12351,48203,12536,10419,987,18061,4809,244,8583,8161,18902,4997,7959,547,902,1527,40766,44829,1,3810,7898,4399,8082,6878,14897,612,27416,1390,27433,3685,1673,12646,2174,23326,2862,725,10122,6758,14627,1035,7581,28500,817,637,7027,930,4482,41756,2796,5548,27853,194,1356,45008,1108,10925,197,2765,3725,45369,15131,46913,262,2170,18470,7050,4525,2163,1,19844,816,12709,5606,30639,13897,1441,8507,35402,5637,65257,6521,255,39196,2180,492,10969,35568,21060,14855,922,5398,24135,21510,760,8598,13071,26253,7180,9546,37514,3232,31240,16737,2736,11590,39566,5432,1689,1936,25160,17722,2478,18550,30726,27924,224,2661,1439,20861,14515,958,295,62558,17507,584,4183,197,2093,13941,5881,2343,14431,2522,1420,1965,361,4053,573,58646,26,29975,1617,20123,26855,4206,2342,14833,6030,21960,1480,299,34403,788,501,15203,9648,11442,4510,3034,1782,27780,64541,5357,5115,2788,1,13463,4106,19686,404,45802,15797,348,8508,1,13801,57706,36891,143,2868,13229,2115,1950,13327,6462,5859,11973,1095,3213,20484,4213,4536,5302,17448,438,1817,7058,369,8042,6283,32027,5074,405,13260,20164,11492,4438,41238,18885,4098,4004,6465,29463,2240,15521,23124,16062,46533,2525,4263,3603,541,584,2366,8942,20713,58575,4685,4100,5482,1773,7002,6727,1438,13574,3817,1,2470,1535,5821,139,21072,1190,11721,7408,6868,15087,36210,1636,3256,139,5144,156,75,5652,658,395,1235,1379,3115,559,2664,14580,712,7081,2022,39685,3125,10260,2846,35125,12127,13081,17481,3366,17910,5724,72,18115,25926,24618,559,17642,2876,243,631,1724,2548,17784,3553,2095,735,2057,1777,5881,315,297,728,883,11940,6051,4113,47801,4790,6276,4269,3643,3620,13304,20842,1638,1237,12874,34788,14827,4563,1438,1633,20602];
A=[68,20,7,144,29,543,15,39,61,526,21,465,334,446,412,88,30,251,212,231,400,129,475,270,4,198,2,90,414,353,288,107,222,8,324,68,526,296,1,351,54,1,123,104,4,261,278,101,374,21,470,54,180,119,461,57,20,176,224,76,109,36,217,7,542,276,13,7,191,80,452,604,76,529,268,115,204,478,5,47,37,556,559,12,295,307,442,91,538,283,802,227,219,273,14,284,504,391,6,67,320,269,78,50,93,127,25,56,65,125,174,4,73,85,186,5,543,146,625,374,112,433,25,65,4,117,52,607,39,67,136,8,301,416,765,226,226,107,258,1,328,425,43,432,12,85,426,62,442,102,206,196,7,35,12,273,3,106,3,15,694,140,6,6,112,74,170,4,142,610,563,317,145,108,213,218,23,285,72,2,621,268,92,400,8,394,46,80,217,187,100,24,25,5,18,42,331,67,212,141,102,325,395,54,287,27,679,183,394,474,84,5,7,379,240,56,190,313,185,319,442,118,202,166,251,47,77,381,148,171,150,1,139,241,359,487,76,51,8,37,199,134,162,33,94,54,562,505,345,339,195,304,268,87,17,9,13,40,124,618,285,12,158,667,578,676,77,235,56,337,341,667,126,234,366,482,60,46,17,290,492,188,77,66,701,131,608,4,110,362,119,555,123,155,143,125,399,64,145,200,273,1,169,104,187,186,289,37,108,13,35,287,515,69,238,518,384,171,12,70,283,168,222,80,1,185,123,103,275,441,247,38,403,6,151,177,367,6,40,104,56,112,33,41,214,235,53,24,474,532,286,203,126,475,842,300,255,169,27,15,73,20,40,145,285,88,35,23,19,74,261,132,119,46,188,427,212,145,64,337,719,251,546,172,548,203,112,4,38,69,15,173,355,240,606,146,22,93,1,69,168,313,10,417,188,85,51,324,452,116,66,135,97,21,130,387,1,160,75,35,3,475,36,60,213,53,41,233,150,313,228,1,32,8,124,430,499,190,28,162,322,33,153,74,553,285,206,84,136,27,217,109,378,319,110,154,269,5,587,325,128,472,268,544,130,733,304,62,31,92,525,20,66,44,1,338,210,65,483,82,369,587,1,12,50,49,280,596,367,166,266,164,44,5,151,366,228,66,481,10,17,49,77,451,197,88,40,84,185,515,237,424,266,97,589,730,110,92,23,91,708,411,398,207,47,46,29,186,366,25,115,27,708,101,127,105,218,68,52,23,3,56,460,453,406,52,161,30,155,9,154,264,325,20,144,595,55,160,173,53,450,534,1,220,143,145,356,313,12,234,126,29,35,495,46,3,190,89,152,112,163,351,288,483,221,1,11,51,15,174,699,75,155,145,36,395,197,641,98,41,562,430,257,352,48,166,10,63,36,441,808,101,32,116,427,95,13,334,259,408,371,182,186,420,75,19,338,66,160,18,114,216,178,211,179,493,74,158,306,99,184,517,196,5,356,514,356,127,382,14,5,189,178,128,1,58,469,294,193,163,446,478,312,581,509,22,36,255,20,42,141,306,121,438,370,87,329,272,708,316,475,38,188,123,312,186,374,99,11,165,37,462,765,4,55,5,350,153,86,111,9,32,711,185,144,7,560,487,496,466,5,285,35,154,240,302,23,346,201,197,244,369,16,599,121,42,437,134,197,17,383,128,122,72,150,4,306,359,753,186,159,164,116,233,1,180,45,80,60,290,299,453,69,380,116,171,238,470,21,372,155,224,137,162,17,297,366,69,3,257,97,774,162,71,557,115,3,89,280,10,139,32,4,335,84,97,116,217,164,37,238,13,86,123,9,151,661,353,64,53,129,231,60,196,719,136,432,435,212,550,37,388,122,8,517,784,53,149,50,21,743,210,139,54,478,731,133,40,4,435,137,15,27,269,7,184,35,155,550,755,599,193,284,377,36,41,72,79,22,286,114,332,122,26,401,215,71,82,32,141,160,195,125,349,25,116,399,31,36,220,418,4,86,282,366,526,250,191,200,301,373,106,188,114,19,110,226,330,1,209,63,290,10,179,48,197,101,52,146,383,30,93,126,138,20,52,53,182,137,323,158,416,5,538,172,104,231,184,171,347,35,247,152,157,31,342,146,633,264,140,225,120,430,22,45,260,30,139,278,486,216,454,33,85,387,567,65,2,89,199,592,100,108,448,248,436,35,551,421,357,684,542,150,85,239,649,102,93,183,2,67,104,292,77,658,67,118,10,218,130,170,305,813,255,265,26,108,276,303,307,183,222,213,231,129,12,94,273,115,51,4,88,567,217,206,141,89,40,227,20,8,272,290,44,156,401,41,337,355,789,119,343,100,129,304,207,786,60,252,3,9,43,58,85,153,1,397,416,524,379,22,275,155,6,99,55,37,39,323,46,171,192,17,473,80,174,350,33,368,43,98,24,155,132,118,24,384,35,78,15,73,204,25,12,30,746,278,117,485,97,298,37,278,149,69,245,138,80,235,24,501,768,78,66,107,6,566,138,96,34,464,610,6,12,139,115,321,295,662,54,130,61,11,220,64,191,409,131,15,284,353,16,14,50,234,256,328,2,81,47,271,345,429,288,21,4,29,37,455,39,48,21,311,397,164,159,370,8,3,150,32,2,76,28,103,131,73,179,254,144,83,109,33,159,61,388,66,335,60,189,169,51,241,546,295,254,227,102,356,219,43,15,5,8,356,12,288,108,412,44,773,318,50,363,541,7,5,659,288,4,90,102,450,174,541,103,683,9,45,793,8,103,606,243,103,84,72,11,7,130,56,314,483,335,16,232,71,120,88,316,391,77,104,59,300,149,112,485,147,244,226,227,110,10,21,26,402,342,44,135,6,175,523,395,505,180,13,132,18,127,430,407,167,363,1,104,178,43,118,56,377,36,56,426,217,111,668,613,44,156,110,307,274,355,30,65,338,39,121,103,136,215,82,76,158,186,256,300,5,14,193,434,37,166,12,157,159,352,144,67,325,364,28,287,541,394,206,360,58,751,286,468,46,345,68,281,194,324,142,92,585,655,85,142,200,89,255,389,25,445,263,581,97,74,327,194,186,118,17,28,21,50,223,23,294,534,582,51,11,95,53,147,33,433,134,20,482,162,189,85,4,26,196,264,95,173,497,5,2,110,174,8,158,355,255,265,47,419,195,208,62,253,179,507,378,569,18,661,181,249,772,108,46,20,292,155,108,669,151,454,637,58,196,190,404,212,139,30,88,89,226,111,154,208,64,277,45,382,597,296,589,47,72,86,10,54,29,214,11,718,518,190,68,408,262,61,45,193,619,199,9,158,10,31,338,103,73,520,51,330,408,57,119,464,280,53,19,327,43,150,357,164,42,271,82,14,112,573,333,207,76,65,323,268,150,76,301,52,184,29,97,703,9,341,69,29,127,17,257,115,48,201,164,534,169,145,51,327,409,12,410,230,13,57,233,51,89,5,319,95,16,1,152,336,69,71,28,381,85,41,248,23,186,456,38,317,62,2,250,240,213,191,207,89,140,611,108,34,487,164,175,11,1,475,93,100,241,285,120,309,92,477,492,605,90,153,620,139,98,59,70,4,17,214,42,318,2,52,421,682,57,123,281,677,433,63,274,140,439,25,91,37,99,152,279,321,391,212,69,22,718,91,233,244,131,58,499,501,31,763,114,55,141,112,220,171,58,178,27,14,567,217,269,10,542,355,166,18,22,20,15,108,335,152,108,122,373,358,40,12,84,81,3,465,43,275,159,276,54,123,219,326,381,785,124,290,55,219,144,167,143,6,652,30,500,140,61,98,252,450,30,103,488,163,240,180,31,283,19,277,441,465,192,55,255,58,302,277,421,105,340,34,335,556,10,121,114,355,55,12,667,585,6,361,6,466,114,53,370,45,97,174,662,160,681,19,232,315,552,150,331,73,447,4,302,55,162,632,61,261,214,505,296,142,280,104,149,118,30,25,250,219,552,113,651,229,403,267,456,99,13,472,122,9,242,383,47,62,372,82,3,164,14,141,390,75,461,34,4,247,131,205,695,453,23,148,471,97,108,116,4,61,723,53,72,50,265,392,477,38,30,465,219,24,257,311,500,3,11,24,77,564,52,190,668,257,24,207,287,60,314,257,160,33,228,79,73,159,663,408,297,348,348,386,809,3,42,20,207,574,28,580,596,22,76,695,416,150,407,634,43,104,377,231,101,369,99,192,639,307,66,499,309,78,53,85,69,306,151,22,307,549,44,21,348,489,49,110,147,1,449,28,815,372,404,129,472,66,76,289,737,359,45,274,115,11,468,7,84,5,204,239,167,7,11,28,124,579,155,790,346,210,32,327,257,67,207,577,76,58,297,23,44,591,45,154,200,175,65,4,256,546,56,487,29,148,50,184,5,340,119,212,56,217,572,72,10,24,2,13,409,505,16,6,447,20,519,453,280,79,240,52,366,416,526,748,705,326,183,658,449,43,41,193,1,71,236,277,244,301,174,11,167,185,25,528,69,82,25,309,269,109,341,3,110,21,110,42,34,74,641,118,286,114,358,157,486,184,326,394,659,22,214,62,79,574,246,156,263,41,77,222,46,40,220,107,4,305,108,15,131,61,188,531,42,654,48,180,128,240,248,578,125,107,32,207,158,372,111,100,18,2,428,163,343,337,530,346,575,386,27,295,55,335,571,74,169,336,249,260,262,619,206,221,193,713,32,18,61,210,232,89,210,81,3,215,62,276,362,8,405,14,587,179,30,162,9,745,318,54,91,61,127,361,56,145,427,171,112,429,117,265,265,297,458,27,208,118,360,5,124,17,326,236,344,194,327,230,129,687,129,274,281,1,169,184,711,58,390,327,242,180,150,34,71,75,167,204,55,274,381,22,524,220,69,108,141,509,60,75,266,174,475,71,217,164,151,577,200,273,272,42,176,19,65,4,380,472,221,51,98,516,429,24,114,406,156,57,130,63,6,7,90,91,154,37,150,9,20,62,91,241,39,709,66,85,284,83,19,330,202,62,418,36,332,45,338,3,253,282,16,48,287,384,85,2,334,203,221,499,64,489,23,12,129,118,299,156,75,13,17,187,49,100,86,78,59,53,13,310,194,183,28,236,95,211,262,298,434,221,179,230,340,80,57,175,47,56,361,175,29,28,38,84,193,87,277,446,784,273,208,230,206,190,9,462,180,212,188,270,43,282,125,571,16,153,160,363,479,148,756,217,1,11,79,10,197,42,152,9,279,1,541,53,685,693,87,700,285,51,146,32,377,347,253,62,618,7,123,383,154,625,222,649,289,503,193,82,545,135,99,468,367,421,72,13,29,210,406,79,50,560,97,78,343,180,55,173,24,15,178,232,138,200,158,264,491,125,418,13,7,128,450,104,219,427,346,15,633,357,283,372,81,93,28,99,123,27,29,185,180,53,251,55,97,9,269,396,408,332,168,14,331,399,158,111,160,89,121,22,190,73,55,46,268,316,327,106,118,81,193,833,94,133,18,22,97,460,100,323,159,276,204,272,98,148,474,17,545,294,493,60,474,103,498,199,29,67,211,149,57,77,196,257,85,51,119,190,305,144,732,115,27,117,7,175,115,1,39,334,62,30,130,121,55,115,12,151,272,251,51,1,103,157,19,94,9,240,11,94,372,510,17,37,179,15,168,6,268,495,400,27,20,6,206,227,95,23,236,31,6,97,326,213,265,149,100,16,7,139,52,273,490,38,21,431,125,95,44,118,438,418,323,1,21,135,272,329,446,281,90,38,229,60,105,102,1,270,32,154,154,218,617,232,116,241,244,52,140,544,293,100,136,47,176,340,87,697,406,490,11,231,35,418,248,455,37,453,90,182,21,48,137,176,9,269,267,31,316,606,4,43,83,582,180,117,218,158,33,750,74,267,376,207,243,19,228,49,21,371,308,286,96,362,339,159,101,110,2,13,270,306,1,427,509,250,175,548,25,17,18,292,167,59,13,509,93,133,29,17,90,28,105,186,122,143,58,353,78,589,61,113,114,306,1,3,206,60,322,6,34,152,465,9,42,435,244,215,470,516,63,51,4,304,149,226,21,122,176,345,247,540,596,305,28,17,374,18,5,235,14,192,13,505,299,126,80,82,28,54,337,603,150,556,87,326,39,202,12,53,51,105,311,45,62,479,12,87,254,158,549,435,134,16,332,98,285,388,20,122,193,412,395,149,550,283,82,648,329,39,147,652,220,432,18,69,604,121,111,31,323,24,106,362,372,5,470,341,47,451,401,203,236,4,106,230,224,25,290,105,27,13,151,145,94,72,362,32,214,382,277,136,38,89,3,389,114,483,175,14,328,100,295,187,397,544,40,238,114,77,726,286,101,68,158,10,822,303,30,2,149,68,100,378,295,14,19,2,11,132,362,8,117,436,26,465,268,54,525,86,87,288,659,128,744,347,111,154,112,12,338,175,167,162,54,715,136,717,86,76,719,334,199,761,73,6,439,447,412,368,6,232,509,47,204,275,30,332,126,317,16,65,505,45,4,67,668,113,14,154,710,168,183,116,437,75,238,5,1,169,461,643,156,202,8,113,118,565,20,498,246,74,113,423,540,9,362,170,75,178,197,149,18,64,150,77,310,86,30,322,136,308,322,266,1,8,558,159,149,488,40,93,506,331,226,101,220,767,176,88,247,182,5,16,203,371,43,665,197,474,17,31,11,348,3,617,421,162,187,224,40,14,279,237,108,542,35,38,204,144,138,437,332,6,115,367,3,577,64,175,147,184,194,342,402,339,74,267,235,186,61,490,36,36,199,175,222,67,424,78,111,778,114,40,489,167,54,25,85,11,708,380,112,347,335,176,211,40,317,222,381,300,121,136,228,120,157,310,739,167,70,64,255,11,15,464,57,808,28,318,470,24,100,220,752,118,617,648,264,427,146,211,7,68,202,310,39,78,33,428,74,187,414,51,4,26,45,394,311,301,83,237,206,51,407,100,460,460,100,554,262,14,745,106,424,80,14,326,2,60,336,48,17,28,152,65,38,108,129,37,48,168,14,174,367,648,226,280,307,295,129,33,648,135,389,252,332,2,98,282,360,105,220,77,493,27,377,12,75,159,4,38,307,297,81,131,3,155,189,344,148,295,403,112,545,535,140,525,86,241,282,439,231,175,8,110,361,94,27,211,551,3,80,34,546,168,15,511,126,263,33,543,578,135,191,2,12,54,30,174,247,15,130,203,75,262,15,455,424,268,37,54,271,1,571,306,658,230,428,409,187,57,333,349,68,100,127,187,461,61,768,219,21,59,68,94,469,140,19,170,228,778,182,36,27,144,154,61,333,281,318,109,270,295,659,390,521,358,91,15,28,31,193,156,347,115,175,25,80,72,588,84,12,7,194,74,278,147,545,433,238,162,118,96,62,139,199,553,146,167,30,56,42,269,491,285,150,153,24,13,358,155,528,399,329,110,45,754,541,40,277,120,783,325,41,349,32,608,132,103,11,448,267,67,67,4,1,13,1,10,154,572,5,11,621,268,266,223,394,238,168,546,183,3,112,63,39,582,254,43,358,147,113,452,52,203,332,30,429,94,2,179,13,124,344,88,505,110,14,294,31,47,500,556,193,162,360,22,114,479,3,362,389,201,27,271,252,32,562,191,451,100,81,65,30,451,102,10,115,41,46,14,328,413,337,254,25,160,145,357,361,235,581,536,316,23,175,113,2,39,207,62,38,60,89,5,54,23,137,248,283,319,667,127,130,542,283,48,42,29,81,114,667,247,308,336,204,77,37,364,88,126,411,11,70,11,286,111,1,293,439,236,568,176,334,245,61,2,247,1,71,483,228,147,44,340,17,23,64,39,217,64,603,7,64,283,321,342,647,18,184,37,276,349,5,384,35,74,476,44,64,451,63,156,122,375,423,75,10,444,91,256,23,567,83,311,50,51,440,319,230,443,7,7,67,93,147,713,53,5,487,641,30,448,492,14,53,207,44,475,175,102,299,156,147,7,125,24,12,67,24,241,99,118,196,89,101,2,182,191,104,167,331,240,224,36,436,27,611,301,188,104,118,473,52,659,183,554,315,104,242,4,58,382,169,52,161,222,169,8,188,1,111,104,60,18,118,52,52,434,236,300,8,204,12,37,141,123,638,192,83,33,9,54,784,1,571,378,50,322,128,492,71,163,43,490,84,159,240,395,150,130,15,26,184,363,93,179,364,214,258,635,366,69,145,653,5,115,184,326,36,120,261,69,318,840,166,14,17,37,396,167,39,25,61,63,307,577,531,62,91,36,27,375,79,14,180,327,130,20,192,5,513,340,201,709,138,350,198,101,317,414,111,394,367,62,391,29,180,49,280,491,8,20,248,123,42,263,45,38,98,94,57,125,278,156,196,14,383,357,315,10,25,68,217,331,13,53,136,350,51,233,501,229,86,195,123,9,277,81,49,356,155,43,84,1,509,310,257,32,105,133,378,101,4,70,118,2,226,223,106,247,434,38,138,51,309,387,138,677,190,296,39,174,66,157,228,569,72,21,175,630,253,9,275,104,149,384,192,235,598,59,26,23,235,103,334,224,482,88,8,503,188,304,627,622,39,649,38,18,163,272,423,217,124,175,546,466,26,8,82,519,174,67,399,294,701,225,9,38,639,704,234,13,547,191,107,292,104,717,268,154,57,346,354,713,27,107,116,358,665,687,192,175,48,145,124,365,91,540,457,452,12,303,177,786,334,111,512,225,3,259,30,156,225,704,102,732,403,145,296,6,17,566,85,83,269,583,4,161,16,432,276,218,96,19,352,370,725,279,182,122,38,251,147,68,644,238,47,571,380,212,324,291,289,347,653,3,267,43,287,65,116,222,31,310,238,38,75,398,20,78,2,21,137,558,527,122,168,91,92,327,341,188,531,29,126,302,58,5,1,302,494,124,492,290,221,21,9,8,221,109,61,115,539,351,104,36,218,66,676,114,179,241,96,109,296,272,25,91,349,616,3,118,176,393,102,139,246,409,59,139,228,7,40,3,4,30,36,24,648,145,85,262,355,341,604,181,14,39,801,522,467,82,631,125,482,24,8,423,13,30,202,479,717,85,414,172,525,314,648,62,49,409,120,445,112,164,14,4,380,48,367,506,61,6,439,86,30,517,149,40,322,73,638,59,270,44,77,23,39,130,175,382,165,94,398,198,385,297,108,386,367,50,27,20,167,146,336,432,88,570,97,193,28,183,5,561,25,479,377,63,398,115,22,548,291,178,339,22,141,64,180,372,37,472,24,123,193,176,421,23,66,109,56,173,10,228,499,181,65,95,648,218,275,329,220,137,713,177,502,257,52,90,16,77,304,5,492,341,178,278,719,313,584,201,234,12,249,432,38,409,465,508,140,271,781,378,543,640,294,280,1,284,16,396,94,359,162,363,47,328,219,448,72,158,217,63,313,719,162,690,34,191,15,259,109,50,220,185,340,645,10,459,212,88,158,64,90,106,49,285,143,549,127,133,444,28,112,74,380,171,72,26,487,154,82,11,549,409,5,418,308,101,91,610,77,371,160,75,47,35,1,108,23,6,12,111,30,756,374,60,223,302,257,304,66,239,16,337,454,325,418,9,534,191,148,2,128,305,55,189,525,564,172,492,59,88,372,395,199,318,208,52,65,142,65,63,95,34,8,4,253,104,612,315,318,270,345,241,18,22,51,175,65,9,752,136,169,401,179,192,162,243,122,32,47,133,600,62,214,217,441,1,129,83,10,363,98,449,87,543,52,130,567,47,9,46,385,11,138,1,355,136,77,684,100,52,403,565,40,359,125,121,28,59,21,195,347,429,41,70,112,72,70,99,413,493,167,165,64,177,28,68,519,47,345,229,195,384,77,471,100,109,79,116,30,79,145,77,393,36,103,26,201,513,66,84,244,48,221,260,78,7,522,37,138,656,73,221,159,16,146,229,17,445,102,106,145,5,95,15,460,626,170,164,711,535,3,149,446,197,66,75,424,17,1,26,333,136,59,275,414,416,63,299,243,463,643,270,215,45,29,14,229,19,513,207,192,772,191,542,94,29,59,449,7,66,23,16,33,265,4,295,329,575,572,394,96,8,617,151,192,1,197,382,573,649,665,154,111,195,378,77,7,231,403,11,71,55,706,22,182,63,67,31,86,160,58,114,366,133,158,297,18,162,222,116,156,43,250,77,376,287,356,583,235,331,472,264,21,109,29,40,195,15,160,328,167,386,16,457,189,130,98,663,233,32,131,33,156,704,331,12,111,153,324,136,108,14,224,100,505,122,271,98,61,150,235,115,36,3,35,100,297,74,147,531,356,13,582,86,85,383,280,119,168,420,43,608,179,459,173,17,102,175,285,177,214,109,644,581,101,11,195,140,563,11,280,175,28,100,135,80,287,19,319,77,187,163,209,46,295,293,3,179,25,140,256,84,333,221,447,120,142,66,5,63,219,57,51,184,426,623,121,437,203,126,55,97,247,13,42,131,203,364,53,213,101,54,283,116,581,425,230,612,232,22,185,438,325,69,1,32,207,194,199,662,461,466,200,50,5,2,19,537,423,74,18,22,171,39,228,169,245,317,130,51,15,60,172,539,582,173,554,407,316,35,293,8,306,48,282,18,53,90,218,51,48,20,238,190,715,151,635,15,252,118,602,299,154,260,232,209,219,141,23,419,460,1,228,150,63,126,141,157,13,520,39,280,519,32,205,66,442,30,15,558,120,266,152,188,396,10,56,522,81,64,589,122,140,731,237,417,555,19,318,3,64,70,789,210,567,22,23,201,128,381,236,1,318,49,144,121,391,438,32,436,375,176,726,77,39,678,158,20,133,773,214,333,14,235,341,565,18,94,176,306,128,181,406,181,394,365,71,147,470,83,58,743,525,218,50,215,332,589,10,48,132,232,507,44,15,683,192,16,63,21,132,150,185,32,225,294,32,37,10,88,11,660,9,562,53,359,522,360,43,511,82,380,19,98,400,32,43,435,223,180,98,50,30,357,695,85,54,206,1,199,116,548,8,507,207,23,131,1,156,592,505,4,33,294,39,731,214,105,115,175,72,210,241,144,83,99,633,25,210,114,306,83,210,580,83,85,323,368,120,74,625,259,141,227,152,643,39,285,330,428,597,68,363,87,65,59,55,196,300,718,176,51,79,19,132,225,506,280,450,1,117,95,435,30,347,34,155,242,155,170,562,159,42,3,121,10,2,156,18,64,218,21,345,84,171,295,33,136,271,680,41,214,124,418,130,212,290,218,438,60,38,281,512,309,13,396,31,7,314,19,250,208,39,173,15,75,298,79,211,6,15,40,200,273,114,479,172,451,86,91,201,201,311,487,19,344,630,245,134,197,111,726];
B=[201,68,602,395,120,654,241,250,410,724,42,565,569,850,830,222,40,307,285,555,445,152,721,495,228,577,516,198,786,731,387,278,697,133,725,700,755,812,2,387,417,2,239,397,123,757,728,284,651,262,551,94,193,393,645,65,58,688,340,608,247,411,720,128,672,504,142,14,632,439,658,822,173,724,376,170,402,707,44,269,83,568,792,15,527,700,645,369,721,284,836,717,307,769,497,582,616,671,108,157,790,299,524,83,579,370,794,192,554,544,247,324,660,296,192,222,734,471,636,762,290,637,29,213,32,226,535,609,74,74,152,78,713,522,772,604,324,750,376,25,573,766,285,778,601,529,573,83,639,354,335,286,10,280,132,443,5,275,10,33,759,305,194,769,246,331,251,90,158,693,635,482,309,270,583,669,326,439,175,14,805,615,742,443,70,421,57,108,383,208,166,342,321,313,75,84,475,235,832,848,213,600,667,139,431,36,703,285,644,705,128,23,125,534,482,428,773,387,562,466,815,166,229,421,812,169,181,482,511,807,267,48,668,464,652,626,212,486,13,105,382,398,515,140,230,612,704,578,839,444,378,678,501,824,562,36,201,156,225,637,764,16,184,740,783,837,760,408,245,787,565,844,181,652,389,782,450,302,67,471,600,252,252,582,710,669,719,22,174,619,700,757,532,271,725,218,583,80,774,228,291,152,724,483,541,567,452,623,635,95,60,793,633,276,557,523,729,196,25,727,726,673,241,288,713,667,308,539,286,698,721,95,448,7,159,475,474,263,107,299,406,337,34,286,402,502,83,59,633,605,666,496,189,769,847,366,466,412,198,223,151,48,732,175,822,575,78,98,412,280,686,183,257,53,483,674,405,323,312,566,776,351,831,460,590,337,715,67,485,152,21,750,398,354,738,407,72,740,38,178,789,622,45,533,293,335,133,768,743,143,472,282,173,48,226,463,193,343,116,47,73,498,41,751,588,750,268,391,615,604,635,7,320,644,536,813,515,200,39,623,624,358,320,195,632,842,742,518,203,34,476,313,752,348,394,304,814,6,638,599,499,662,285,742,735,828,738,85,47,196,570,147,627,96,77,743,300,512,599,105,759,645,121,21,59,131,467,698,383,622,487,272,566,137,806,417,427,523,641,51,129,70,469,759,552,268,181,404,269,523,477,663,686,330,710,798,204,119,29,760,828,453,816,217,160,525,792,779,652,112,310,108,779,234,270,374,761,87,190,643,4,149,713,558,829,69,504,597,445,138,202,453,725,23,257,629,548,686,294,78,495,711,140,672,236,535,741,836,290,295,392,33,112,850,249,6,631,252,292,251,638,690,620,610,223,67,542,160,34,491,754,312,388,574,53,406,617,670,387,76,692,732,456,618,201,555,20,492,127,488,839,153,229,753,483,151,254,629,361,593,469,278,247,623,89,175,476,199,209,793,368,632,255,567,641,702,683,286,396,103,212,780,263,31,650,571,612,627,738,19,104,304,357,316,406,321,722,334,316,536,646,600,797,724,827,26,148,269,51,400,639,312,160,515,701,230,651,435,785,358,673,764,787,578,710,679,405,618,267,545,39,547,839,169,507,103,450,369,758,206,181,129,785,548,180,23,603,742,807,729,795,641,114,238,706,847,72,479,218,272,256,809,232,613,150,224,772,158,201,22,577,503,688,419,176,135,571,497,775,695,399,230,246,574,2,240,673,780,363,296,723,522,71,567,125,591,287,570,31,467,250,467,470,329,123,423,463,221,60,668,437,822,402,78,623,709,4,359,524,726,735,65,58,474,148,367,195,730,233,556,726,22,807,124,77,186,736,812,192,366,283,605,493,707,834,819,579,571,345,615,123,423,157,338,554,813,324,320,102,235,765,272,173,290,711,788,276,718,696,570,382,115,130,742,9,194,458,452,657,778,681,248,580,659,121,141,782,87,73,387,188,487,449,119,625,692,497,317,37,181,620,362,168,759,98,564,514,89,257,314,700,783,99,501,437,810,831,723,762,642,448,193,240,466,659,607,789,628,798,477,386,454,655,460,594,489,231,67,155,435,88,119,201,175,22,183,294,184,164,694,486,455,274,675,178,286,360,195,718,434,96,796,206,457,213,417,357,774,769,333,275,199,478,66,90,570,428,418,807,818,624,508,320,581,516,850,790,696,178,391,840,813,139,638,400,524,194,708,609,361,746,665,289,201,300,679,201,549,503,194,341,671,348,348,672,517,311,23,587,170,207,383,836,724,475,102,393,722,553,351,190,634,449,696,267,65,501,529,497,515,12,92,607,325,453,535,532,73,453,196,16,628,450,818,358,707,544,418,540,811,534,468,261,517,513,500,836,724,265,19,467,48,68,142,613,150,425,486,731,408,189,301,325,10,239,522,645,131,644,78,280,460,501,761,118,188,397,124,822,123,225,54,603,277,123,495,631,77,293,92,144,478,151,52,606,832,548,243,814,166,451,43,431,201,88,564,208,659,274,37,589,804,715,795,824,17,655,210,117,218,466,831,196,530,256,481,710,583,844,75,204,741,13,701,536,818,499,321,473,633,768,18,162,147,280,400,757,6,346,203,639,612,444,672,204,10,446,102,655,352,532,394,482,403,738,674,462,144,14,237,822,22,607,47,204,688,330,239,508,309,364,315,37,675,681,400,669,649,110,577,222,164,740,571,724,729,233,499,595,312,61,119,231,46,409,18,615,135,543,218,833,676,586,421,588,340,10,690,332,97,574,848,802,318,567,490,814,18,719,818,21,109,796,269,424,269,82,22,9,249,188,450,583,702,122,819,386,143,288,393,545,473,513,198,305,269,761,647,550,555,631,811,176,676,25,76,648,388,369,260,693,786,651,708,772,183,123,183,643,831,774,723,516,446,9,370,212,279,454,776,701,145,80,539,289,181,836,706,63,354,472,761,547,456,322,408,776,296,167,551,453,544,151,848,654,724,299,520,210,36,329,671,455,266,42,435,434,619,322,152,736,420,586,368,643,495,428,402,647,782,462,618,624,486,224,324,369,398,348,314,845,746,426,493,228,180,622,475,149,461,488,667,478,383,601,666,474,147,147,30,236,77,724,43,472,818,583,556,43,175,323,178,232,583,154,456,664,213,681,324,8,42,234,348,179,291,668,7,332,185,592,61,264,424,788,850,266,482,281,506,231,466,344,602,756,642,23,674,733,269,836,125,527,65,363,271,426,820,649,595,665,162,317,443,733,490,476,154,380,297,535,180,187,211,196,527,743,605,621,315,678,82,534,168,48,143,111,486,25,737,780,830,317,708,622,126,114,456,740,235,173,778,14,69,593,298,120,708,176,339,660,185,272,488,724,578,26,351,310,224,540,784,281,452,144,630,191,673,341,352,324,102,362,498,184,685,487,149,842,835,425,847,26,373,234,51,218,186,481,433,88,246,577,593,427,502,259,349,848,20,472,337,83,74,332,78,459,660,669,189,262,176,383,787,250,395,37,425,299,307,503,47,491,687,384,519,619,73,255,367,318,412,594,146,247,652,711,181,498,798,228,211,9,659,150,170,555,496,563,580,99,554,785,709,114,486,811,160,125,125,846,378,210,742,106,359,736,520,527,782,340,624,778,686,598,318,467,472,504,168,152,63,777,307,296,357,399,251,159,23,792,442,501,830,264,88,657,784,496,808,405,344,166,797,278,580,406,337,406,24,754,305,341,57,687,741,322,384,28,22,563,439,616,348,191,141,698,444,54,824,378,424,792,497,196,533,738,652,62,215,243,372,610,840,153,603,147,791,196,664,229,630,694,41,564,190,210,100,354,491,127,408,630,493,400,262,242,383,56,514,454,621,251,182,325,384,628,436,646,817,608,368,606,715,125,152,215,573,191,71,815,812,7,381,8,568,122,237,843,71,108,224,664,202,796,24,250,669,607,203,447,437,491,71,600,576,436,680,135,810,375,635,364,166,340,336,411,302,64,698,314,750,763,171,847,296,538,511,789,155,25,755,157,816,523,463,322,88,569,95,425,845,223,520,432,234,566,107,19,337,244,277,717,466,509,362,698,424,120,322,67,483,812,547,353,81,312,536,541,519,55,538,800,27,335,845,735,257,13,150,230,847,88,651,743,455,451,530,555,827,496,448,165,211,332,119,230,204,846,454,447,781,388,707,830,8,806,105,241,582,55,591,817,88,99,847,602,309,680,666,610,796,730,591,635,414,431,827,786,517,774,673,472,812,506,224,527,398,238,64,349,673,131,65,533,559,71,774,777,2,454,63,828,518,420,610,532,186,366,494,781,636,200,535,673,311,514,81,390,161,597,465,284,63,179,329,227,708,719,837,393,475,153,389,664,560,478,639,85,129,745,56,309,600,93,611,331,418,604,36,688,756,105,516,94,669,88,304,26,421,260,601,123,442,678,142,354,171,54,378,609,759,291,12,469,142,850,593,733,311,424,578,548,575,773,767,792,790,308,733,743,93,54,551,3,260,834,411,268,612,741,48,647,600,130,614,81,187,548,458,753,122,664,4,704,205,184,63,147,333,664,143,429,825,486,751,613,259,610,661,768,237,325,468,113,836,384,655,778,128,368,409,763,201,567,261,11,377,130,104,555,77,833,555,482,832,791,602,413,675,460,757,251,163,230,815,460,551,458,513,80,382,776,459,585,415,797,796,696,712,772,563,395,358,787,190,420,380,448,519,406,811,219,555,225,715,133,25,754,294,512,796,587,211,300,503,617,382,574,349,675,557,689,604,94,300,88,790,321,244,174,91,189,386,274,432,566,357,483,675,467,451,495,311,710,426,389,170,429,8,222,35,509,439,505,410,697,614,424,755,735,720,420,439,291,690,767,177,440,377,255,196,780,91,192,335,512,390,318,286,560,715,850,820,79,711,437,565,69,460,322,237,692,84,323,816,404,587,720,723,744,64,251,32,126,116,482,651,279,88,195,677,588,179,153,444,181,81,143,507,258,322,550,127,167,141,286,93,46,127,339,326,114,825,512,254,429,233,103,605,246,705,838,401,489,310,451,86,845,288,25,239,593,412,741,170,675,239,548,670,271,506,256,233,675,400,382,397,356,241,132,322,50,199,164,738,94,110,64,588,452,285,72,251,320,737,542,536,541,281,626,394,375,151,386,426,464,699,737,699,47,101,88,96,310,218,764,654,804,286,642,626,589,243,797,535,182,497,455,774,150,716,467,777,55,236,794,557,847,255,817,278,182,174,668,171,204,46,820,16,575,4,593,234,759,703,113,735,627,283,603,101,666,704,605,390,714,203,152,477,277,743,447,657,483,542,196,86,616,188,359,703,835,473,165,27,37,634,786,85,62,816,848,372,676,538,414,359,49,46,624,260,647,447,381,581,537,190,766,15,154,153,628,260,704,627,499,32,834,798,343,495,478,592,38,550,828,205,227,282,424,400,654,356,187,358,489,429,834,618,810,149,583,505,840,548,382,171,132,182,597,352,65,69,484,708,555,368,762,138,623,836,243,211,366,103,332,621,116,584,356,719,647,828,100,819,533,176,590,748,515,244,693,246,535,824,186,108,551,727,704,110,378,541,387,642,842,256,608,258,798,205,89,505,619,234,706,7,96,622,171,457,237,558,118,242,24,175,591,256,69,7,280,475,80,349,652,279,269,95,708,830,95,191,180,335,760,55,706,699,773,202,139,9,385,265,477,281,399,285,142,459,718,219,270,628,649,26,39,570,57,453,815,670,28,460,240,189,130,720,713,752,396,2,332,191,292,706,496,411,770,527,262,660,135,103,12,498,165,545,478,747,710,255,207,293,465,79,443,651,377,414,612,503,512,480,251,754,432,650,13,365,185,480,580,793,66,512,426,454,412,762,476,345,801,370,540,256,768,677,6,319,334,733,266,346,700,616,514,811,163,355,492,421,781,154,549,52,584,578,805,506,126,422,377,335,361,577,30,16,303,332,3,585,811,281,719,820,332,24,729,641,731,482,97,554,551,479,59,511,330,223,452,725,222,371,95,548,116,813,70,147,307,366,11,88,383,813,425,8,37,575,707,508,132,449,426,261,758,670,472,149,28,358,176,547,43,810,248,357,621,643,791,502,150,94,422,40,111,249,30,422,68,523,432,594,230,153,616,316,619,668,617,767,189,599,163,220,44,336,485,114,781,46,495,689,49,241,393,258,653,805,141,32,559,647,521,699,97,388,679,585,598,532,577,659,809,804,440,283,217,727,307,732,618,77,612,139,322,115,403,54,656,644,569,279,718,567,395,812,625,399,559,159,719,308,310,71,443,334,349,24,293,323,110,742,423,57,272,420,631,668,819,226,6,471,135,669,795,179,354,167,348,244,754,650,179,510,305,820,800,343,116,185,241,428,833,628,435,143,397,324,117,607,373,38,128,3,189,187,484,127,608,625,579,589,543,112,792,458,303,331,820,248,850,701,162,822,686,22,383,299,402,241,438,812,286,795,264,148,748,640,405,836,405,207,721,573,551,384,65,639,584,626,344,498,122,494,285,627,209,418,590,291,413,120,693,265,56,632,748,628,341,295,665,482,649,8,7,510,725,791,545,426,90,141,364,813,88,836,266,92,131,455,633,90,368,379,419,576,629,522,841,121,555,148,411,245,48,819,141,311,399,395,9,84,673,451,464,509,91,100,618,448,371,119,377,812,181,348,371,193,119,18,436,410,260,693,722,566,172,107,241,377,8,800,709,801,822,307,98,679,401,398,128,600,136,49,360,169,385,779,669,8,222,419,4,708,101,299,827,304,620,566,502,571,321,510,262,439,88,641,350,748,284,238,582,116,677,708,657,841,467,274,556,271,433,377,130,379,717,812,372,542,432,475,516,251,541,454,630,384,665,654,430,157,511,591,849,555,97,170,575,177,47,479,111,814,153,555,719,114,117,788,813,465,637,677,279,529,311,217,385,387,225,425,284,647,44,783,225,319,464,112,74,530,571,673,648,713,170,389,406,449,655,354,629,811,253,674,570,248,802,625,492,777,50,675,12,299,720,140,86,41,459,488,77,214,458,261,155,662,20,357,816,683,560,414,395,486,184,694,792,418,653,389,780,8,384,402,384,143,817,513,610,45,699,32,428,416,670,53,644,486,161,265,4,762,326,600,586,455,585,641,712,544,211,534,521,407,470,452,291,205,655,366,768,300,121,295,830,14,367,44,576,200,39,575,132,298,196,754,748,166,268,55,488,112,33,476,377,225,537,342,178,788,99,557,537,660,508,93,753,29,754,385,763,351,765,815,470,89,538,435,416,348,148,480,578,235,781,698,31,628,228,757,529,505,62,800,584,822,391,138,199,188,794,621,632,756,450,646,760,548,804,607,699,685,662,192,226,290,284,653,477,210,491,167,524,78,788,262,25,354,503,313,338,238,685,527,300,654,430,548,162,262,534,584,616,651,47,63,60,417,517,665,238,193,29,29,753,277,693,679,506,126,156,821,616,175,614,210,812,411,678,451,306,701,176,179,39,801,694,146,219,15,275,35,134,177,192,629,343,544,672,358,816,441,502,401,415,730,187,544,146,120,639,622,517,81,413,778,492,680,309,282,460,335,831,272,70,218,203,283,696,823,606,540,54,448,453,65,609,611,746,191,591,56,596,580,482,702,824,202,375,716,391,494,602,581,846,199,131,763,157,631,391,45,495,95,73,295,529,672,731,283,155,633,403,361,480,368,796,556,780,391,528,686,276,540,281,233,462,226,126,10,630,59,169,688,457,444,824,698,461,658,480,379,652,74,303,826,670,507,395,648,219,344,364,707,156,470,519,74,122,25,749,784,351,618,710,571,796,765,428,684,452,500,515,11,200,846,256,700,96,371,374,66,239,69,555,362,652,10,221,405,543,415,670,40,218,138,520,477,6,442,326,809,505,353,565,684,183,213,299,521,507,605,47,536,351,516,69,775,107,462,225,201,645,788,667,573,121,352,352,258,149,771,245,6,491,836,788,815,594,46,523,645,212,678,198,270,495,741,467,29,183,647,26,244,35,485,119,290,561,670,414,22,260,332,296,232,738,525,449,54,546,41,631,826,448,253,203,477,331,730,280,792,752,401,510,14,153,681,796,465,536,324,185,12,306,202,366,458,799,128,320,425,563,506,472,367,9,301,75,144,236,623,760,258,626,93,418,77,813,6,659,660,208,593,350,778,167,382,478,743,470,312,432,456,731,460,54,446,830,446,490,663,657,316,492,780,496,304,223,685,8,314,273,709,385,161,738,571,547,847,226,100,60,589,540,168,786,77,74,684,533,794,554,468,512,146,36,458,144,416,186,467,316,177,195,35,715,539,807,740,260,461,570,467,663,529,158,703,740,128,793,49,456,65,363,502,29,21,756,326,162,562,196,553,190,348,96,358,763,387,512,33,751,572,782,628,283,95,667,361,25,118,232,775,86,460,820,387,705,334,162,275,732,149,679,360,199,120,209,68,717,354,501,126,111,409,640,166,13,344,441,13,771,622,109,719,764,129,157,98,819,454,568,699,383,347,123,380,174,191,663,727,106,308,656,644,681,16,337,693,484,407,403,453,704,187,152,66,824,144,750,279,840,589,9,808,846,426,813,693,186,677,134,71,282,336,496,560,213,427,584,626,100,117,164,701,214,125,656,830,720,583,637,468,707,734,466,186,591,577,544,387,156,847,365,594,820,352,848,722,32,500,715,409,770,783,453,521,831,156,708,400,641,738,536,685,46,601,694,818,629,118,716,343,10,681,174,213,313,724,243,749,664,189,397,9,279,725,312,111,349,717,12,470,40,790,492,224,776,134,697,562,782,302,223,192,317,499,190,447,832,637,342,714,627,469,435,419,597,503,711,4,473,382,304,94,272,653,453,506,369,183,733,523,632,391,615,611,435,813,824,136,186,437,383,517,382,298,664,42,411,394,360,55,114,339,556,486,578,753,223,148,181,190,383,356,807,203,640,728,135,135,481,137,734,343,258,290,259,194,332,545,122,596,481,835,14,544,389,584,245,772,353,414,103,595,255,234,127,513,225,124,92,228,808,211,118,667,541,451,630,234,188,597,808,590,470,642,839,304,492,75,326,709,32,808,527,508,820,398,595,227,553,456,651,122,113,752,772,666,166,188,316,39,657,169,567,711,135,114,757,378,38,529,434,54,468,315,787,646,614,302,546,125,64,136,766,796,415,440,529,207,510,314,663,599,476,539,291,213,504,413,594,748,141,590,145,550,256,187,743,594,48,531,775,66,410,154,99,722,634,265,358,78,517,316,423,532,212,736,367,794,682,367,441,626,206,156,97,364,63,326,584,213,178,825,651,591,286,560,352,720,758,494,694,799,101,110,96,106,507,29,569,473,845,341,734,526,800,362,381,108,835,692,790,674,582,655,420,430,826,586,638,659,562,358,3,557,531,613,181,562,570,435,88,676,221,524,136,169,301,307,443,793,257,719,274,364,28,295,459,501,335,657,793,774,342,548,447,519,178,453,780,307,389,789,745,565,231,225,448,48,365,95,802,462,333,79,518,256,404,18,742,467,59,506,438,137,339,767,239,505,600,350,187,670,24,263,26,412,424,356,176,801,467,400,649,831,267,330,282,485,50,571,839,484,661,47,825,355,319,14,435,759,336,439,692,584,299,543,331,732,647,496,486,750,280,124,622,778,402,552,699,58,637,5,475,516,676,354,475,676,562,640,254,54,71,541,528,10,809,191,174,695,341,619,173,496,374,745,78,530,656,157,584,426,535,224,418,234,82,407,324,548,231,633,144,167,785,185,40,84,474,442,787,96,726,510,199,774,474,72,409,620,294,664,213,782,432,569,34,212,509,556,178,105,343,163,81,198,816,547,548,490,786,697,30,622,538,496,757,520,227,542,79,552,660,545,328,200,38,780,349,100,583,380,425,487,571,799,472,412,338,486,369,588,605,15,587,498,724,677,91,356,640,207,236,342,157,720,184,154,698,378,540,775,764,710,821,509,820,548,120,229,835,460,281,124,734,206,264,264,337,198,275,720,552,624,591,766,333,514,779,324,690,70,205,38,622,610,675,462,385,837,197,789,128,36,775,682,603,98,708,109,235,293,509,338,534,588,740,534,587,25,714,170,695,314,329,626,631,819,817,730,816,276,772,306,88,311,727,144,520,521,747,513,513,157,723,92,208,773,137,243,549,315,573,833,579,438,281,129,835,46,379,612,450,535,545,655,563,450,499,557,242,175,182,135,277,18,362,475,618,722,150,693,758,448,109,816,252,610,421,464,242,769,777,780,709,319,537,191,256,198,354,263,577,208,543,584,145,274,277,765,132,112,169,121,594,396,664,707,416,21,762,194,720,548,840,395,186,464,102,844,407,515,181,113,818,762,506,738,628,229,823,788,476,35,249,213,822,27,292,462,248,289,613,691,289,108,373,257,477,302,716,314,840,694,4,243,55,336,308,396,484,522,538,153,797,119,108,75,235,135,188,636,474,696,249,620,511,780,201,599,814,142,172,447,688,483,88,339,185,171,370,339,748,669,338,693,349,177,392,448,771,236,152,172,488,554,206,739,487,840,585,119,197,15,203,676,630,129,36,641,583,110,845,212,641,555,382,353,47,295,313,706,610,344,572,433,442,38,830,61,709,755,331,226,312,382,845,66,132,106,640,531,735,364,689,272,309,265,720,807,224,395,575,218,657,242,49,833,817,223,523,266,220,205,256,352,14,773,212,669,834,54,250,447,764,128,228,829,138,366,344,317,497,43,69,547,105,86,666,226,796,813,320,746,616,344,402,4,229,430,819,842,655,93,39,295,217,696,399,2,431,637,440,382,820,524,693,714,445,601,796,108,49,812,491,23,755,785,363,423,31,717,713,586,464,244,452,384,441,690,516,641,451,395,333,319,538,116,75,782,729,583,456,294,495,664,76,308,175,493,605,93,172,757,816,59,348,810,632,813,629,57,353,761,321,247,37,139,27,799,13,595,65,781,835,836,392,514,219,424,477,661,446,287,260,546,351,540,713,417,436,445,842,158,235,482,100,626,425,610,17,536,484,628,533,12,306,642,823,259,99,604,344,767,309,247,794,468,722,356,336,168,696,220,670,47,242,289,613,143,752,693,841,121,511,769,206,357,688,362,476,295,202,710,106,702,693,767,734,111,530,176,768,791,372,291,517,802,525,56,469,607,665,383,685,355,714,12,307,284,487,53,700,109,552,688,481,455,742,350,459,193,299,477,70,652,143,123,340,142,668,338,271,744,75,480,422,740,153,220,249,467,235,624,626,261,634,240,49,712,746,617,64,517,395,35,421,55,613,216,76,176,207,218,633,103,453,11,124,773,434,757,416,660,263,574,353,108,281,758,831,692,22,452,745,328,385,557,256,840];